/****************************************************************************\
*                                                                            *
*  Copyright 2008 The CAnt2 Project (http://code.google.com/p/cant2)         *
*                                                                            *
*  Licensed under the Apache License, Version 2.0 (the "License");           *
*  you may not use this file except in compliance with the License.          *
*  You may obtain a copy of the License at                                   *
*                                                                            *
*      http://www.apache.org/licenses/LICENSE-2.0                            *
*                                                                            *
*  Unless required by applicable law or agreed to in writing, software       *
*  distributed under the License is distributed on an "AS IS" BASIS,         *
*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  *
*  See the License for the specific language governing permissions and       *
*  limitations under the License.                                            *
*                                                                            *
\****************************************************************************/

#ifndef INCLUDED_HASHTABLE_H__
#define INCLUDED_HASHTABLE_H__

#include "EnableIf.h"
#include "TypeTraits.h"

#include <vector>
#include <stdexcept>

/****************************************************************************/

template < bool C, typename T, typename F > struct SelectType { typedef T Type; };
template < typename T, typename F > struct SelectType<false,T,F> { typedef F Type; };

/****************************************************************************/

// This hash table implementation is inspired by the hash table 
// implementation used in the Lua interpreter.

// This container is roughly equivalent to a 
// TR1::unordered_multimap<unsigned,T> in terms of functionality, though 
// not in terms of interface.

// This container should be able to be used to implement any of the 
// TR1::unordered_* containers, if desired.  For example 
// TR1::unordered_multimap<K,V>::insert(k,v) would be implemented as 
// HashTable<pair<k,v>>::insert(ComputeHash(k),pair(k,v)); 

template < typename T > class HashTable
{
    typedef HashTable Self;

public:
    static const unsigned Invalid = ~0u;
    static const unsigned MinSize = 16;

    explicit HashTable ( size_t reserveCapacity = 0 )
        : table     ( NextPowerOfTwoSize ( reserveCapacity ) )
        , firstFree ( unsigned ( table.size() - 1 ) )
        , usedCount ( 0 )
    {
    }

    void swap ( HashTable& other )
    {
        other.table.swap ( table );
        std::swap ( other.firstFree, firstFree );
        std::swap ( other.usedCount, usedCount );
    }

    void Insert ( const unsigned hash, typename SelectType < IsSimpleValueType<T>::Value != 0,T,T&>::Type v )
    {
        InsertInternal ( hash, v );
    }

    void Remove ( const unsigned p )
    {
        if ( p >= table.size() ) return;
        RemoveInternal ( p );
    }

    unsigned FindFirstMatching ( const unsigned hash ) const
    {
        unsigned p = MainPosition ( hash );
        return FindInternal ( p, hash );
    }

    unsigned FindNextMatching ( unsigned p, const unsigned hash ) const
    {
        if ( p < table.size() ) p = table[p].next;
        return FindInternal ( p, hash );
    }

    size_t Used() const
    {
        return usedCount;
    }

    size_t Capacity() const
    {
        return table.size();
    }

    const T& Get ( unsigned p ) const
    {
        if ( p >= table.size() ) throw std::out_of_range("Invalid hash position");
        return table[p].value;
    }

    T& Get ( unsigned p )
    {
        return const_cast < T& > ( static_cast < const Self* > ( this )->Get ( p ) );
    }

private:
    static size_t NextPowerOfTwoSize ( size_t v )
    {
        v |= ( v >>  1 );
        v |= ( v >>  2 );
        v |= ( v >>  4 );
        v |= ( v >>  8 );
        v |= ( v >> 16 );
        v += 1;
        if ( v < MinSize ) v = MinSize;
        return v;
    }

private:
    unsigned MainPosition ( unsigned hv ) const
    {
        return hv & ( table.size() - 1 );
    }

    unsigned FindPrev ( unsigned p0, unsigned tp ) const
    {
        for (;;)
        {
            unsigned np = table[p0].next;
            if ( np == tp ) return p0;
            p0 = np;
        }
    }

    unsigned FindInternal ( unsigned p, const unsigned hash ) const
    {
        for (;;)
        {
            if ( p >= table.size() ) return Invalid;
            const Node& n = table[p];
            if ( n.IsUnused() ) return Invalid;
            if ( n.hash == hash ) return p;
            p = n.next;
        }
    }

    void InsertInternal ( unsigned vh, typename SelectType < IsSimpleValueType<T>::Value != 0,T,T&>::Type v )
    {
        unsigned p0 = MainPosition ( vh );
        Node& n0 = table[p0];
        unsigned vnn = Node::NoNext;
        Node* vn = &n0;
        if ( !n0.IsUnused() )
        {
            Node& fn = table[firstFree];
            unsigned p1 = MainPosition ( n0.hash );
            if ( p1 == p0 )
            {
                vn = &fn;
                vnn = n0.next;
                n0.next = firstFree;
            } else
            {
                table [ FindPrev ( p1, p0 ) ].next = firstFree;
                fn.swap ( n0 );
            }
        }

        usedCount += 1;
        vn->SetWithSwap ( vnn, vh, v );

        for ( ;; )
        {
            Node& fn = table[firstFree];
            if ( fn.IsUnused() ) return;
            if ( firstFree == 0 ) break;
            firstFree -= 1;
        }

        Self tmp ( table.size() * 2 );
        for ( unsigned i = 0; i < table.size(); ++i )
        {
            Node& n = table[i];
            if ( !n.IsUnused() )
            {
                tmp.InsertInternal ( n.hash, n.value );
            }
        }

        tmp.swap ( *this );
    }

    void RemoveInternal ( unsigned p )
    {
        unsigned p0 = MainPosition ( table[p].hash );
        if ( p != p0 )
        {
            unsigned p1 = FindPrev ( p0, p );
            table[p1].next = table[p].next;
        } else
        if ( table[p].HasNext() )
        {
            unsigned n = table[p].next;
            table[p].swap ( table[n] );
            p = n;
        }

        Node& node = table[p];
        T defaultT = T();
        node.SetWithSwap ( Node::UnusedNext, 0, defaultT );
        usedCount -= 1;
        if ( firstFree < p ) firstFree = p;
    }

private:
    struct Node
    {
        unsigned next;
        unsigned hash;
        T value;

        static const unsigned UnusedNext = ~0u;
        static const unsigned NoNext     = ~1u;

        Node() : next ( UnusedNext )
        {
        }

        void swap ( Node& other )
        {
            std::swap ( other.next, next );
            std::swap ( other.hash, hash );
            SwapValue ( other.value, value );
        }

        template < typename T > static typename EnableIf < IsSimpleValueType<T>::Value != 0,void>::Type SwapValue ( T& v1, T& v2 )
        {
            std::swap ( v1, v2 );
        }

        template < typename T > static typename DisableIf < IsSimpleValueType<T>::Value != 0,void>::Type SwapValue ( T& v1, T& v2 )
        {
            v2.swap ( v1 );
        }

        void SetWithSwap ( unsigned next, unsigned hash, T& value )
        {
            this->next = next;
            this->hash = hash;
            SwapValue ( this->value, value );
        }

        bool IsUnused () const { return next == UnusedNext; }
        bool HasNext  () const { return next != NoNext; }
    };

private:
    std::vector < Node > table;
    unsigned firstFree;
    size_t usedCount;
};

#endif /* #ifndef INCLUDED_HASHTABLE_H__ */

